Chùa được dựng từ khi nào cũng chưa có tài liệu nào ghi chính xác, nhưng chùa Kiến Sơn được võ sư Trương Ma Ni cải tạo và xây dựng từ thời nhà Đinh. Gia Cát Thị khi soạn Tân đính hiệu bình Việt điện u linh tập 3, tờ 110 ở Phù Đổng Thiên Vương truyện chép: "Thần Vương tức Thiên Vương. Xưa thời Hùng Vương có công chinh phạt định nước, nhận phong ở đây. Đến khi họ Triệu bị người Hán thôn tính, đất đai biên giới đều bị nội thuộc, lại trải binh họa đốt cháy, đền miếu tiêu điều. Miếng ngói tức rường tán mất gần hết… Gặp có nhà sư Trương Ma Ni tìm được đúng dấu xưa. Bèn hưng công xây dựng danh lam, mở mang đất đai, để làm nơi thờ Phật đốt hương, gọi tên là chùa Kiến Sơ. Bên phải cửa trước chùa lại dựng một miếu thổ thần để làm nơi tụng đọc kinh sách".[1]

Trước đó, vào năm 820, thiền sư Vô Ngôn Thông từ Trung Quốc sang được sư Cảm Thành khi đó trụ trì tại chùa tôn làm thầy, từ đó mở ra dòng thiền Vô Ngôn Thông.

Vua Lý Công Uẩn khi còn đi tu thường lui tới chùa học kinh. Tương truyền tại chùa ông đã được Thánh Gióng báo mộng qua bài thơ

Bài thơ dự báo nhà Lý truyền được 8 đời, và sẽ kết thúc vào thời một vị vua có chữ Nhật ở trên chữ Sơn (tức vua Lý Huệ Tông tên là Sảm). Sau này lên làm vua, Lý Thái Tổ rời đô về Thăng Long, đã cho trùng tu chùa và đền Phù Đổng cạnh đó. Vua cũng nhiều lần đến thăm chùa, và mời thiền sư Đa Bảo (là đời thứ 5 dòng thiền Vô Ngôn Thông) về Thăng Long bàn luận. Khi dòng thiền Vô Ngôn Thông suy thoái, chùa trở thành nơi thờ cả Tam giáo: Phật, Lão, Khổng